package com.leetcode.二叉树.深度优先.迭代遍历;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 遍历顺序：
 *	前序遍历：中->左->右
 *	中序遍历：左->中->右
 *	后序遍历：左->右->中
 * 二叉树的迭代遍历算法是利用栈(stack)先进后出的特点，只有栈弹出的时候才算是访问，入栈只是保证访问顺序 
 * 
 *二叉树的每一个节点都可以看成是中间节点，只不过是有没有左右子树的区别而已。二叉树的所有遍历算法都是利用这个来实现的！！！！！！！！！
 *
 *统一迭代算法就是：前、中、后序遍历的代码相似，不用大幅度修改。
 *
 *思路：每个节点都要当成是中间节点
 *1、先将root入栈
 *2、进入循环：while(栈不为空）
 *	取出栈顶元素node，如果node不为空，然后根据遍历的顺序，重新入栈（入栈的顺序跟遍历的顺序相反）
 *	入栈中间节点时（也就是本身），入栈后需要再入栈一个null来标记
 *	如果node为空，则node指向null的下一个，也就是中间节点，此时将node输出（放进result里）
 *回到第二步，继续。
 *
 *为什么以上两步就可以实现三种遍历呢？
 *其实，模拟一遍就会发现，每一个节点都会入栈两次，当我们取出一个节点后，要根据遍历的顺序，重新入栈
 *此时的中间节点就是第二次入栈，而它的左右子树是第一次，所以我们要用null来标记中间节点是第二次入栈，
 *当遇到null，表示null的下一个是二次入栈的，则取出直接放进result就可以了。
 *所以对于每一个节点（看成是中间节点），只要是没有被null标记，说明不是第二次入栈的。
 *则取出（第一次出栈），然后根据遍历的顺序，重新将它自己、左子树、右子树三者分别入栈
 *所以，调整顺序，就可以实现三种遍历了
 *
 *看文字题解可能想象不出，只要模拟画一遍就清晰了。
 */
public class 统一迭代算法 {
	/**
	 * 前序遍历
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		if(root != null) stack.push(root);
		while(!stack.isEmpty()) {
			TreeNode node = stack.pop();//获取栈顶元素，并出栈
			if(node != null) {
				//此时node当作是中间节点，按顺序入栈（入栈的顺序跟遍历顺序相反，栈嘛，先进后出嘛）
				if(node.right != null) stack.push(node.right);
				if(node.left != null) stack.push(node.left);
				stack.push(node);//自己就是中间节点
				stack.push(null);//入栈null，作为标记，则null的下一个就是中间节点
			}else {
				node = stack.pop();//此时node指向的就是中间节点
				result.add(node.val);
			}
		}
		return result;
    }
	
	/**
	 * 中序遍历
	 */
	 public List<Integer> inorderTraversal(TreeNode root) {
			List<Integer> result = new ArrayList<>();
			Deque<TreeNode> stack = new LinkedList<TreeNode>();
			if(root != null) stack.push(root);
			while(!stack.isEmpty()) {
				TreeNode node = stack.pop();//获取栈顶元素，并出栈
				if(node != null) {
					//此时node当作是中间节点，按顺序入栈（入栈的顺序跟遍历顺序相反，栈嘛，先进后出嘛）
					if(node.right != null) stack.push(node.right);
					stack.push(node);//自己就是中间节点
					stack.push(null);//入栈null，作为标记，则null的下一个就是中间节点
					if(node.left != null) stack.push(node.left);
				}else {
					node = stack.pop();//此时node指向的就是中间节点
					result.add(node.val);
				}
			}
			return result;
	 }
	 
	 /**
	  * 后序遍历
	  */
	 public List<Integer> postorderTraversal(TreeNode root) {
			List<Integer> result = new ArrayList<>();
			Deque<TreeNode> stack = new LinkedList<TreeNode>();
			if(root != null) stack.push(root);
			while(!stack.isEmpty()) {
				TreeNode node = stack.pop();//获取栈顶元素，并出栈
				if(node != null) {
					//此时node当作是中间节点，按顺序入栈（入栈的顺序跟遍历顺序相反，栈嘛，先进后出嘛）
					stack.push(node);//自己就是中间节点
					stack.push(null);//入栈null，作为标记，则null的下一个就是中间节点
					if(node.right != null) stack.push(node.right);
					if(node.left != null) stack.push(node.left);
				}else {
					node = stack.pop();//此时node指向的就是中间节点
					result.add(node.val);
				}
			}
			return result;
	 }
}
